package backtracking.other;

import java.util.*;

/**
 * 332. 重新安排行程
 * <p>
 * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
 * <p>
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
 * <p>
 * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
 * <p>
 * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
 */
public class N332_ReconstructionItinerary {
    private Deque<String> res;
    private Map<String, Map<String, Integer>> map;

    private boolean backtracking(int ticketNum) {
        if (res.size() == ticketNum + 1) return true;
        String last = res.getLast();
        if (map.containsKey(last)) {
            for (Map.Entry<String, Integer> t : map.get(last).entrySet()) {
                Integer count = t.getValue();
                if (count > 0) {
                    res.add(t.getKey());
                    t.setValue(count - 1);
                    if (backtracking(ticketNum)) return true;
                    t.setValue(count);
                    res.removeLast();
                }
            }
        }
        return false;
    }

    public List<String> findItinerary(List<List<String>> tickets) {
        map = new HashMap<>();
        res = new LinkedList<>();
        for (List<String> t : tickets) {
            Map<String, Integer> temp;
            if (map.containsKey(t.get(0))) {
                temp = map.get(t.get(0));
                temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
            } else {
                temp = new TreeMap<>();
                temp.put(t.get(1), 1);
            }
            map.put(t.get(0), temp);
        }
        res.add("JFK");
        backtracking(tickets.size());
        return new ArrayList<>(res);
    }

    public static void main(String[] args) {
        N332_ReconstructionItinerary solution = new N332_ReconstructionItinerary();
        String[][] t = {{"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}};
        List<List<String>> tickets = new ArrayList<>(t.length);
        for (String[] strs : t) {
            List<String> ticket = new ArrayList<>();
            for (String str : strs) ticket.add(str);
            tickets.add(ticket);
        }
        List<String> list = solution.findItinerary(tickets);
        for (String s : list) {
            System.out.print(s + " ");
        }
    }
}
